\chapter{Ээээээ}

По лекции от 8 сентября 2011 года.

\section{Лектор}

{\large Александр Владимирович Омельченко}
\par\bigskip

e-mails : \hfill avo-travel@yandex.ru
\par\bigskip

Дислокация в АФТУ : \hfill где-то на шестом
\par\bigskip

\section{Литература}

\begin{itemize}
\item Комбинаторика. Веленкин. (Обратить внимание на задачи)

\item Введение в комбинаторные методы дискретной математики. Сачков. (Читать не интересно)

\item Ведение в комбинаторный анализ. Рыбников. (Опять же читать не интересно)

\item Лекции о произодящих функциях. Лондо. (Читать на производящих функциях...)

\item Введение в комбинаторный анализ. Риордан.

\item Комбинаторика. Холл

\item Комбинаторная математика. Райзер.

\item Книга J. H. van Lint и R. M. Wilson

\item Комбинаторика для программистов. В. Липский (читать в обязательном порядке)

\item Конкретная математика. Кнут, Поташник и банда
\end{itemize}

\section{Ликбез для чайников}

\begin{Def}
	Законы де Морагана:
	\[
		\begin{split}
			& \overline{\left( A \cup B \right)} = \bar A \cap \bar B \\
			& \overline{\left( A \cap B \right)} = \bar A \cup \bar B
		\end{split}
	\] 
\end{Def}

\begin{Def}
	Система подмножеств множества $X = \{x_1, ... , x_n\}$:
	\[
		S_X = \{ X_1, ... , X_k\}, X_i \subset X
	\]
\end{Def}

\begin{Def}
	Система подмножеств $S_X$ - покрытие, если \[ \cup_{i=1}^k X_i = X \]
\end{Def}

\begin{Def}
	Покрытие $S_X$ - разбиение, если \[ \left(\forall i \right) \left[ X_i \not= \emptyset \right] \land \left( \forall i \not= j \right) \left[ X_i \cap X_j = \emptyset \right] \]
	$X_i$ - блок разбиения.
\end{Def}

\paragraph{Примечание}

Иногда важен порядок блоков разбиения, в этом случае говорят об упорядоченном разбиении.

\begin{Def}
	Упорядоченное разбиение $S_X$, в котором допускаются $X_i = \emptyset$, называется разделением.
\end{Def}

\begin{Def}
	Пусть $X_1, ... , X_n$ - множества, тогда прямое произведение этих множеств:
	\[
		X_1 \times ... \times X_n = \{\left( a_1, ... , a_n \right) : a_i \in X_i \}
	\]
	(т. е. прямое произедение - множество векторов)
\end{Def}

\begin{Def}
	Мультимножество - множество с кратным вхождением элементов в него (в отличие от обычного множества, элементы могут входить в него несколько раз).
	Обычно говорят, что мультимножество построено над множестом, элементы которого содержит.
	Также мультимножесто называется $k$-сочетанием с повторениями из $n$, где $n$ - мощность множества, а $k$ - мощность мультимножества.
	Если порядок элементов играет роль, то говорят о $k$-размещении с повторениями из $n$
\end{Def}

\begin{Def}
	Правило суммы в комбинаторике:
	\[
		A \cap B = \emptyset \Rightarrow \left| A \cup B \right| = \left| A \right| + \left| B \right|
	\]
\end{Def}

\begin{Def}
	Правило произведения в комбинаторике:
	\[
		\left| A \times B \right| = \left| A \right| \cdot \left| B \right|
	\]
\end{Def}

\section{$k$-сочетания без повторений}

Пусть $X$ - множество, причем $\left| X \right| = n$. Требуется найти количество $k$-элементных подмножеств множества $X$. Число таких подмножеств называется $k$-сочетанием без повторений и обозначается $\binom{n}{k}$ или по старому $C_n^k$ (читается: количество сочетаний из $n$ по $k$)

Попробуем определить это число, для этого, выберем в исходном множестве произольный элемент $x_1$. Разобьем множество $\sum_k$ всех $k$-элементных подмножеств множества $X$, на два множества:

\begin{itemize}
\item в первое ($\sum_k^1$) попадают только те подмножества множества $X$, которые содержат $x_1$

\item в второе ($\sum_k^2$) попадают те, которые не содержат $x_1$
\end{itemize}

Мощность первого легко выразить заметив, что один из $k$ элементов всегда определен, остается выбрать лишь $k-1$, причем выбирать их можно из $n-1$ элементов, т. к. повторения не допускаются, следовательно:

\begin{equation}
	\left| \sum\nolimits_k^1 \right| = \binom{n-1}{k-1}
\end{equation}

Мощность второго легко определить, исходя из того, что нужно выбрать $k$ элементов опять же из $n-1$ вариантов, т. к. эти $k$-подмножества не должны содержать $x_1$, следовательно:

\begin{equation}
	\left| \sum\nolimits_k^2 \right| = \binom{n-1}{k}
\end{equation}

Итоговое реккурентное выражение получаем сложением (не забыв добавить граничные условия) :

\begin{equation}
	\begin{split}
		& \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \\
		& \binom{n}{0} = 1, \forall n = 0, 1, 2, ... \\
		& \binom{n}{k} = 0, \forall k > n \ge 0
	\end{split}
	\label{math::recurrent_binom}
\end{equation}

Теперь используя полученное соотношение можем построить треугольник Паскаля, для подсчета биномиальных коэффициентов:

\[
	\setcounter{MaxMatrixCols}{15}
	\begin{matrix}
		&&&&& 1 \\
		&&&& 1 && 1 \\
		&&& 1 && 2 && 1 \\
		&& 1 && 3 && 3 && 1 \\
		& 1 && 4 && 6 && 4 && 1 \\
		1 && 5 && 10 && 10 && 5 && 1\\
	\end{matrix}
\]

Видно, что треугольник Паскаля обладает симметрией, которая выражается в виде следующей формулы:

\begin{equation}
	\binom{n}{k} = \binom{n}{n-k}
\end{equation}

Докажем еще одну формулу (суммирование по верхнему индексу):

\begin{equation}
	\binom{n+1}{m+1} = \sum_{k=0}^n \binom{k}{m} = \sum_{k=m}^{n} \binom{k}{m}
\end{equation}

\begin{Proof}
	\[
		\begin{split}
			& \binom{k+1}{m+1} = \binom{k}{m} + \binom{k}{m+1} \Rightarrow \binom{k}{m} = \binom{k+1}{m+1} - \binom{k}{m+1} \Rightarrow \\
			& \Rightarrow \sum_{k=0}^n \binom{k}{m} = \sum_{k=0}^n \left[ \binom{k+1}{m+1} - \binom{k}{m+1} \right] = \\
			& = \sum_{k=0}^n \binom{k+1}{m+1} - \sum_{k=0}^n \binom{k}{m+1} = \\
			& = \binom{n+1}{m+1} + \sum_{k=0}^{m-1} \binom{k+1}{m+1} + \sum_{k=m}^{n-1} \binom{k+1}{m+1} - \sum_{k=0}^m \binom{k}{m+1} - \sum_{k=m+1}^n \binom{k}{m+1} = \\
			& = \binom{n+1}{m+1} + \sum_{k=m}^{n-1} \binom{k+1}{m+1} - \sum_{k=m+1}^n \binom{k}{m+1} = \\
			& = \binom{n+1}{m+1} + \sum_{k=m+1}^n \binom{k}{m+1} - \sum_{k=m+1}^n \binom{k}{m+1} = \binom{n+1}{m+1}
		\end{split}
	\]
\end{Proof}

\paragraph{Историческая справка}

\[\binom{n}{k}\] называется биномиальным коэффициентом по назанию биномиальной теоремы:

\begin{equation}
	\left( x + y \right) ^n = \sum_{k=0}^n \binom{n}{k}x^k y^{n-k}
	\label{math::binom}
\end{equation}

Подставляя в \ref{math::binom} частные значения $x$ и $y$ можно получать очень интересные выражения:

\begin{equation}
	\begin{split}
		& x = y = 1 \\
		& 2^n = \sum_{k=0}^n \binom{n}{k}
	\end{split}
\end{equation}

\begin{equation}
	\begin{split}
		& x = -y = 1 \\
		& 0 = \sum_{k=0}^n \left(-1\right) ^k \binom{n}{k}
	\end{split}
\end{equation}

Теперь продифференцируем исходное выражение по $x$:

\begin{equation}
	n \left( x + y \right) ^{n-1} = \sum_{k=0}^n \binom{n}{k} k x^{k-1} y^{n-k}
\end{equation}

И рассмотрим его частные случаи:

\begin{equation}
	\begin{split}
		& x = y = 1 \\
		& n 2^{n-1} = \sum_{k=0}^n k \binom{n}{k}
	\end{split}
\end{equation}

\section{$k$-сочетания с повторениями}

\begin{Def}
Число $k$-мультимножеств над множеством мощности $n$ называется количестом сочетаний из $n$ по $k$ с повторением. Обозначается как
\[
	\left( \binom{n}{k} \right)
\]
\end{Def}

Для сочетний с повторениями справедлива формула:

\begin{equation}
	\left( \binom{n}{k} \right) = \binom{n+k-1}{k}
\end{equation}

\begin{Proof}
	Занумеруем элементы множества натуральными числами и далее будем работать с подможеством натуральных чисел. Таким образом каждое сочетание может быть предствалено неубывающей (т. е. есть повторения чисел) выборкой $a_1 \le a_2 \le ... \le a_k$, где $a_i \in \left[ 1 .. n \right]$

	Теперь уеличим каждый элемент следующим образом $\tilde {a_i} = a_i + (i - 1)$. Таким образом получим выборки из различных элементов $\tilde {a_1} < \tilde {a_2} < ... < \tilde {a_k} $. Теперь все элементы выборок лежат в интервале $\left[ 1 .. n+k-1 \right]$ и все они различны, а исходная задача сводится к подсчету числа $k$-сочетаний без повторений из $(n+k-1)$.

	(Такой метод назыается принципом биекции в комбинаторике, т. е. мы перешли от произвольных элементов к натуральным числам построив биективное отображение, после чего решили задачу для нового множества, а значит, из-за биективности, и для старого)	
\end{Proof}

Докажем еще одно равенство:
	\[
		\left( \binom{n+1}{k} \right) = \binom{n+k}{k} = \binom{n+k}{n} = \sum_{i=0}^k \binom{n+k-i-1}{n-1}	
	\]

\begin{Proof}
	Разделим множество $k$-элементных мультимножеств над исходным множестом на нумерованные блоки $X_i$. Для этого зафиксируем в исходном множестве $X$ элемент $x_1$. В $X_i$ входят только те $k$-сочетния, в котрых кратность элемента $x_1$ входит $i$ раз. Тогда мощность блока можно выражается следующим образом:

	\[
		\left| X_i \right| = \left( \binom{n}{k-i} \right)
	\]
	Просуммируем по всем $i$ от $0$ до $k$ и получим:
	\[
		\sum_{i=0}^k\left| X_i \right| = \sum_{i=0}^k \left( \binom{n}{k-i} \right) = \sum_{i=0}^k \binom{n+k-i-1}{k-i} =\sum_{i=0}^k \binom{n+k-i-1}{n-1}
	\]
\end{Proof}

Немного преобразуем индексы:
	\[
		\left( \binom{n+2}{k-1} \right) = \binom{n+k}{k-1} = \binom{n+k}{n+1} = \sum_{i=0}^{k-1} \binom{n+k-i-1}{n}
	\]
В итоге получаем:

\begin{equation}
	\binom{n+k}{n+1} = \sum_{i=0}^{k-1} \binom{n+k-i-1}{n}
\end{equation}

Теперь рассмторим частные случаи последней функции:

\begin{equation}
	\begin{split}
		& n = 0 \\
		& \binom{k}{1} = \sum_{i=0}^{k-1} \binom{k-i-1}{0} = 1 + ... + 1 = k
	\end{split}
\end{equation}

\begin{equation}
	\begin{split}
		& n = 1 \\
		& \binom{k+1}{2} = \sum_{i=0}^{k-1} \binom{k-i}{1} = k + (k-1) + ... + 1 = k \cdot \frac{1+k}{2}
	\end{split}
\end{equation}

\begin{multline}
	n = 2 \\
	\binom{k+2}{3} = \sum_{i=0}^{k-1} \binom{k-i+1}{2} = \\
	= \sum_{i=0}^{k-1} \frac{k^2 - k i + i^2 - i}{2} = \sum_{i=0}^{k-1} \frac{k^2 - (k + 1) i + i^2}{2}
\end{multline}

\begin{multline}
	n = 3 \\
	\binom{k+3}{4} = \sum_{i=0}^{k-1} \binom{k-i+2}{3} = \\
	= \sum_{i=0}^{k-1} \frac{k^3-3k^2(i-1)+k(i^2-i-1)-(i^3-3i^2+2i)}{6} = \\ = \sum_{i=0}^{k-1} \frac{(k^3+3k^2-k)-i(3k^2+k+2)+i^2(k+3)+i^3}{6}
\end{multline}

\section{Домашние задания}

\paragraph{Задание 1.} Доказать следующее равенство:

\begin{equation}
	\sum_{k=0}^n \binom{m+k}{k} = \binom{m+n+1}{n}
\end{equation}

\begin{Proof}
	Доказательство состоит в многократно применении формулы \ref{math::recurrent_binom} к правой части, посмотрим, что при этом получается:
	\[
		\begin{split}
			& \binom{m+n+1}{n} = \binom{m+n}{n-1} + \binom{m+n}{n} = \\ 
			& = \binom{m+n-1}{n-2} + \binom{m+n-1}{n-1} + \binom{m+n}{n} = ... = \\
			& = \binom{m}{-1} + \binom{m}{0} + \binom{m+1}{1} + ... + \binom{m+n-1}{n-1} + \binom{m+n}{n}
		\end{split}
	\]
	Первое слагаемое равно нулю и его можно отбросить, все остальные образуют сумму равную сумме в левой части.
\end{Proof}

Другое доказательство

\begin{Proof}
	\[
		\sum_{k=0}^n \binom{m+k}{k} = \sum_{k=0}^n \binom{m+k}{m}
	\]
	Теперь сделаем небольшую замену:
	\[\tilde n = m + n\] тогда можно сказать, что $m+k = \overline{m .. \tilde n}$ Получаем выражение нового вида:
	\[
		\sum_{\tilde k=m}^{\tilde n} \binom{\tilde k}{m} = \binom{\tilde n + 1}{m + 1} = \binom{m + n + 1}{m + 1} = \binom{m+n+1}{n}
	\]
\end{Proof}

\paragraph{Задание 2.} Доказать следующее равенство:

\begin{equation}
	\sum_{i=0}^k \binom{n}{i} \cdot \binom{m}{k-i} = \binom{n+m}{k}
\end{equation}

\begin{Proof}
	Пусть есть два непересекающихся множества $N$ и $M$, причем $\left| N \right| = n$, а $ \left| M \right| = m $. Число способов, которым можно выбрать k элементов из их объединения выражается, с одной стороны формулой \[\binom{n+m}{k}\]. С другой стороны, количество способов складывется из количества способов выбора $k$-элементов из $M$ + количество способов выбора $(k-1)$ элементов из $M$ и одного из $N$ и т. д. В общем виде каждое слагаемое определяется соотношением:

	\[
		\binom{m}{k-i} \cdot \binom{n}{i}
	\]

	Т. е. на каждом этапе мы выбираем $(k-i)$ из $M$ и $i$ элементов из $N$, а всего выбираем $k$ элементов. Суммирую по $i$ от $0$ до $k$, получаем количество всех возможных сочетаний из $n+m$ по $k$ элементов, а это как раз и есть левая часть исходного выражения.
\end{Proof}

\paragraph{Задание 3.} Доказать следующее реккурентное соотношение для сочетаний с повторениями:

\begin{equation}
	\begin{split}
		& \left( \binom{n}{k} \right) = \left( \binom{n-1}{k} \right) + \left( \binom{n}{k-1} \right) \\
		& \left( \binom{n}{1} \right) = \binom{n}{1} = n \\
		& \left( \binom{n}{k} \right) = \binom{1 + k - 1}{k} = 1
	\end{split}
\end{equation}

\begin{Proof}
	Доказательство построим по принципу аналогичному сочетаниям без поторений. Зафиксируем элемент $x_1 \in X$, и разобьем все k-мультимножества над $X$ на два множества:

\begin{itemize}
	\item Первое ($\sum_k^1$) - содержит мультимножества содержащие $x_1$

	\item Второе ($\sum_k^2$) - содержит мультимножества не содержащие $x_1$
\end{itemize}

Мощность первого подмножества определяется из соображений, что входящие мультимножества сожержат один элемент $x_1$, остальные (k-1) элементов находятся сочетанием с повторениями из n (а не из (n-1), т. к. $x_1$ также может повториться в мультимножестве), в итоге имеем:
	\[
		\left| \sum\nolimits_k^1 \right| = \left( \binom{n}{k-1} \right)
	\]
Мощность второго множества находится проще, т. к. все его элементы не содержат $x_1$, нужно просто выбрать k элементов из множества без $x_1$, т. е:
	\[
		\left| \sum\nolimits_k^2 \right| = \left( \binom{n-1}{k} \right)
	\]
Остается только добавить граничные условия.

\end{Proof}

\paragraph{Задание 4.} Сколькими способами можно выбрать две кости домино, так чтобы их можно было приложить? (Для тех кто не знает, что такое домино, кость домино имеет две половины, на каждой из них стоит от 0 до 6 точек. В наборе есть кости всех сочетаний, т. к. кость домино - 2-сочетание с повторениями из 7 - всего 28. Две кости домино прикладываются, если у каждой из них есть полоина с равным числом точек)

\begin{Solution}
	Рассмотрим различные приложения костей домино (по совмещаемому число точек). Количество костей, на которых присутсвует половина с 0 меток, равно 7. Любая пара из них прикладывается, количество различных вариантов приложений: \[ \binom{7}{2} = 21 \] Аналогичное утверждение справедливо для любого числа точек, а значит общее число вариантов: \[ 7 \cdot \binom{7}{2} = 7 \cdot 21 = 147 \]
\end{Solution}

\paragraph{Задание 5.} Рота состоит из трех офицеров, 6 сержантов и 60 рядовых. Сколько существует различных способов формирования отряда из 1 офицера, 2 сержантов и 20 рядовых?

\begin{Solution}
	Просто ответ: \[ \binom{6}{1} \cdot \binom{6}{2} \cdot \binom{60}{20} \]
\end{Solution}
